package algorithm.action;

import datastructure.TreeNode;

public class ReconstructBinaryTree {

	public static void main(String[] args) {
		int[] preOrder = {1,2,4,7,3,5,6,8};
		int[] inOrder = {4,7,2,1,5,3,8,6};
		TreeNode tree = reconstructBinaryTree(preOrder, inOrder);
		showTree(tree);
	}
	
	static TreeNode reconstructBinaryTree(int[] pre, int[] in) {
		if(pre.length <= 0) return null;
		
		int[] pre_l = null, pre_r = null, in_l = null, in_r = null;
		int pos = -1;
		for(int i = 0; i < in.length; i++) {
			if(pre[0] == in[i]) {
				pos = i;
				break;
			}
		}
		pre_l = new int[pos]; in_l = new int[pos];
		pre_r = new int[in.length-pos-1]; in_r = new int[in.length-pos-1];
		
		for(int i = 0; i < pos; i++) {
			pre_l[i] = pre[i+1];
			in_l[i] = in[i];
		}
		
		for(int j = pre.length-1; j > pos; j--) {
			pre_r[j-pos-1] = pre[j];
			in_r[j-pos-1] = in[j];
		}

		TreeNode treeNode = new TreeNode(pre[0]);
		treeNode.left = reconstructBinaryTree(pre_l, in_l);
		treeNode.right = reconstructBinaryTree(pre_r, in_r);
		return treeNode;
	}
	
	static void showTree(TreeNode treeNode) {
		if(treeNode == null) return;
		showTree(treeNode.left);
		System.out.print(treeNode.val);
		showTree(treeNode.right);
	}
}
